Stochastic Calculus

1. Introduction to Finite Markov Chains

Definition

A sequence of random variables $(X_{0}, X_{1}, X_{2}, . . .)$ is a Markov chain with state space $Ω$ and transition matrix $P$ if
for all $n \geq 0$ , and all sequences $(x_{0}, x_{1}, . . ., x_{n}, x_{n + 1})$ , we have that

P [X_{n + 1} = x_{n + 1} | X_{0} = x_{0}, . . ., X_{n} = x_{n}]

= P [X_{n + 1} = x_{n + 1} | X_{n} = x_{n}] = P (x_{n}, x_{n + 1}) .

Classical Markov Chains

Gambler's ruin

recall the gambler's ruin problem we once discussed in Intro To Probability. It turns out that we may use Markov Chains to model it.

Coupon Collecting

Irreducibility and Aperiodicity

Definition

A transition matrix P is called irreducible, if
for any $x, y \in Ω$ , there exists a number n (possibly depending on $x, y$ )
such that

P^{n} (x, y) > 0.

this means that it is possible to get from any state to any other state using only transitions of positive probability.

Definition

For any $x \in Ω$ , define $T (x) = {n \geq 1 : P^{n} (x, x) > 0}$ . The period of
state x is the greatest common divisor of $T (x)$ , denoted by $g c d (T (x))$ .

essentially $T (x)$ is the set of times when it is possible for the chain to return to starting position x.

Lemma

If P is irreducible, then $g c d T (x) = g c d T (y)$ for all $x, y \in Ω$ .

proof. Fix two states x and y. There exist non-negative integers r and $ℓ$ such that $P^{r} (x, y) > 0$ and $P^{ℓ} (y, x) > 0$ . Letting $m = r + ℓ$ , we have $m \in T (x) \cap T (y)$ . Now consider the set

S = {r + ℓ + n | n \in T (y)}

Let d be the period of $T (y)$ . The $S = {r + ℓ + k d | k \in N}$ which is basically an arithmetic progression of step size $d$ .However since $S \subseteq T (x)$ the difference in this elements must be divisible by the period of $T (x)$ which we denote to be $D$ . That is $d % D = 0$ . By a complete parallel argument we also have $D % d = 0$ . Therefore this implies that $d = D$ or $g c d (T (x)) = g c d (T (y))$ as desired.

Definition

For an irreducible chain, the period of the chain is defined to be the period which is common to all states. The chain is aperiodic if all states have period 1.

Example

random walk on on N-cycle where N is odd is aperiodic

First realize to return to the same state you either go an element then make a U turn back, leading to an even contribution to the time to return

eg: 0 \to 1 \to 2 \to 1 \to 0

or you make a cycle which is either odd or even depending depending on N.
So it is clear in odd cycles there exists both a return time of 2(go to next then return back) and some odd number. In which case the gcd of all return times can only be 1. This will apply to all states.

Theorem

If P is irreducible and aperiodic, then there exists an integer r such that

P^{n} (x, y) > 0, \forall x, y \in Ω, \forall n \geq r .

Stationary Distributions

Notations

Ω : state space

μ : measure on j Ω

P, Q : transition matrices | Ω | \times | Ω |

f : function on Ω

$ρ P : measure on Ω$
$P Q : transition matrix$
$P f : function on Ω$

Associative

$(μ P) Q = μ (P Q)$
$(P Q) f = P (Q f)$

Consider a Markov chain with state space $Ω$ and transition matrix P.
Recall that

P [X_{n + 1} = y | X_{n} = x] = P (x, y) .

• $μ_{0}$ : the distribution of $X_{0}$
• $μ_{n}$ : the distribution of $X_{n}$
Then we have that
• $μ_{n + 1} = μ_{n} P$ .
• $μ_{n} = μ_{0} P^{n}$ .
• $E [f (X_{n})] = μ_{0} P^{n} f$ .

Definition

We call a probability measure $π$ is stationary if

π = π P .

If $π$ is stationary and the initial measure $μ_{0}$ equals $π$ , then

μ_{n} = π, \forall n .